package com.li.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class Test39 {

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    /**
     * 通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，
     * 随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
     */
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
//        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(2, node1, null);

        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(2, node5, null);

        TreeNode root = new TreeNode(1, node3, node6);
        System.out.println(new Test39().isSymmetric(root));
    }
}
